UVa/11481 - Arrange the Numbers/11481.cpp

   1 /*
   2   Problem: 11481 - Arrange the Numbers
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6   Algorithm: Inclusion-exclusion principle
   7
   8   Accepted.
   9  */
  10
  11 using namespace std;
  12 #include <algorithm>
  13 #include <iostream>
  14 #include <iterator>
  15 #include <sstream>
  16 #include <fstream>
  17 #include <cassert>
  18 #include <climits>
  19 #include <cstdlib>
  20 #include <cstring>
  21 #include <string>
  22 #include <cstdio>
  23 #include <vector>
  24 #include <cmath>
  25 #include <queue>
  26 #include <deque>
  27 #include <stack>
  28 #include <map>
  29 #include <set>
  30
  31 const int N = 1000, mod = 1000000007;
  32
  33 long long choose[N+1][N+1], fact[N+1];
  34
  35 void prepare(){
  36   /* Factorials */
  37   fact[0] = fact[1] = 1;
  38   for (int i=2; i<=N; ++i) fact[i] = (fact[i-1]*i)%mod;
  39
  40   /* Binomial coefficients */
  41   for (int i=0; i<=N; ++i) choose[i][0] = choose[i][i] = 1;
  42   for (int i=1; i<=N; ++i)
  43     for (int j=1; j<i; ++j)
  44       choose[i][j] = (choose[i-1][j-1] + choose[i-1][j])%mod;
  45 }
  46
  47 int main(){
  48   prepare();
  49
  50   int C, pizza = 1;
  51   scanf("%d", &C);
  52   while (C--){
  53     int n, m, k;
  54     scanf("%d %d %d", &n, &m, &k);
  55
  56     long long ans = 0;
  57     for (int i=0; i<=m-k; ++i){
  58       ans += (i & 1 ? -1 : 1) * (choose[m-k][i] * fact[n-k-i]) % mod;
  59       ans %= mod;
  60     }
  61
  62     ans =  ((ans * choose[m][k]) % mod + mod) % mod;
  63
  64     printf("Case %d: %lld\n", pizza++, ans);
  65   }
  66   return 0;
  67 }